/**
 * Created with IntelliJ IDEA.
 * Description: 练习 KMP算法
 * User: 86187
 * Date: 2022-10-06
 * Time: 12:18
 */
public class KMP {
    /**
     * kmp算法实现
     * @param str 主串
     * @param sub 子串
     * @param pos 从主串的pos下标开始比较
     * @return 返回子串在主串额位置
     */
    public static int kmp(String str,String sub,int pos) {
        if(str == null || sub == null) return -1;

        int lenStr = str.length();
        int lenSub = sub.length();
        if(lenStr == 0 || lenSub == 0) return -1;

        if(pos < 0 || pos >= lenStr) return -1;

        // 求next数组
        int[] next = new int[lenSub];
        getNext(sub,next);

        int i = pos; // 遍历主串
        int j = 0; //遍历子串

        while(i < lenStr && j < lenSub) {
            if(j == -1 || str.charAt(i) == sub.charAt(j)) {
                ++i;
                ++j;
            } else {
                j = next[j];
            }
        }

        if(j >= lenSub) return i - j;
        return -1;
    }
    private static void getNext(String sub,int[] next) {
        // 代码能进到这个函数 说明子串至少有一个字符
        next[0] = -1;
        // 若子串只有一个字符, 就直接返回
        int lenSub = sub.length();
        if(lenSub == 1) return;
        // 代码走到这 说明子串至少有两个字符
        next[1] = 0;

        int k = 0;
        int i = 2;
        while(i < lenSub) {
            // k == -1 时,说明第一次就匹配失败或者回退时一直没有匹配成功
            if(k == -1 || sub.charAt(i-1) == sub.charAt(k)) {
                next[i++] = ++k;
            } else {
                k = next[k];
            }
        }
    }


    public static void main(String[] args) {
        System.out.println(kmp("ababcabcdabcdefabc", "aabaabab", 0)); //
        System.out.println(kmp("ababcabcdabcdefabc", "a", 0)); //0
        System.out.println(kmp("ababcabcdabcdefabc", "abcd", 0)); //5
        System.out.println(kmp("ababcabcdabcdefabc", "fabc", 0)); //14
    }
}
